//
// Created by 张亦乐 on 2018/12/11.
//

#ifndef SKIPLIST_RADIXTREE_HPP
#define SKIPLIST_RADIXTREE_HPP

#include <vector>
#include <string>
#define ALPHABET_SIZE 26
struct trie_node
{
    int count;
    trie_node* children[ALPHABET_SIZE];
};
trie_node* create_node()
{
    trie_node* node = new trie_node();
    node->count = 0;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        node->children[i] = nullptr;
    }
    return node;
}

void insert_node(trie_node* root,const char* key)
{
    trie_node* node = root;
    const char* p = key;
    while(*p)
    {
        if(node->children[*p - 'a'] == nullptr)
        {
            node->children[*p - 'a'] = create_node();
        }
        node = node->children[*p - 'a'];
        ++p;
    }
    node->count++;
}

int search_node(trie_node* root,char* key)
{
    trie_node* node = root;
    char* p = key;
    while(*p && node != nullptr)
    {
        node = node->children[*p - 'a'];
        ++p;
    }
    if(node == nullptr)
        return 0;
    else
        return node->count;
}

//递归搜索
void RecursiveSearch(trie_node* node,const char* prefixword,std::vector<std::string>& vec)
{
    char prefixbuff[50] = {0};
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        if(node->children[i] != nullptr)
        {
            snprintf(prefixbuff,50,"%s%c",prefixword,char(i+97));
            RecursiveSearch(node->children[i],prefixbuff,vec);
        }
    }
    if(node->count > 0)
    {//说明是个单词
        vec.emplace_back(prefixword);
    }
}

std::vector<std::string> complete_me(trie_node* root,const char* prefix)
{
    trie_node* node = root;
    std::vector<std::string> candidateWord;
    const char* p = prefix;
    while(*p)
    {
        node = node->children[*p - 'a'];
        p++;
    }

    if(node == nullptr)
    {
        return candidateWord;
    }

    RecursiveSearch(node,prefix,candidateWord);

    return candidateWord;
}


#endif //SKIPLIST_RADIXTREE_HPP
